import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ${USER}
 * Date: ${YEAR}-${MONTH}-${DAY}
 * Time: ${TIME}
 */
public class Main {

    public static List<String> topKFrequent(String[] words, int k) {

        //1、计算每个单词出现的次数
        Map<String, Integer>  map = new HashMap<>();
        for (String s : words) {
            if(map.get(s) == null) {
                map.put(s, 1);
            } else {
                int val = map.get(s);
                map.put(s,val + 1);
            }
        }

        //2、已经统计完毕，创建小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });


        //遍历 Map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String s = minHeap.poll().getKey();
            ret.add(s);
        }

        Collections.reverse(ret);
        return ret;
    }
    public static void main(String[] args) {

        String[] words = {"i", "b", "v", "i", "v", "d"};
        System.out.println(topKFrequent(words, 3));
    }
}